// 684. [并查集]冗余连接
// https://leetcode.cn/problems/redundant-connection/
// https://leetcode.cn/problems/count-servers-that-communicate/
// 删去边后剩余一棵树
// 树可以看成是一个连通且 无环 的 无向 图。
// 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。
// 添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。
// 图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai
// 和 bi 之间存在一条边。 请找出一条可以删去的边，删除后可使得剩余部分是一个有着
// n 个节点的树。 如果有多个答案，则返回数组 edges 中最后出现的边。 示例 1：
// 输入: edges = [[1,2], [1,3], [2,3]]
// 输出: [2,3]
// 示例 2：
// 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
// 输出: [1,4]
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x) freopen("d:/oj/" #x ".in", "r", stdin)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
  vector<size_t> vtParent_;  // p[i] = j,表示i的父是j
  size_t findParent(size_t i) {
    if (vtParent_[i] != i) {
      vtParent_[i] = findParent(vtParent_[i]);
    }
    return vtParent_[i];
  }
  void unionNode(size_t n1, size_t n2) {
    vtParent_[findParent(n1)] = findParent(n2);
  }

 public:
  vector<int> findRedundantConnection(vector<vector<int>> edges) {
    vtParent_.resize(edges.size() + 1);
    for (size_t i = 1; i <= edges.size(); i++) {
      vtParent_[i] = i;
    }
    for (auto edg : edges) {
      size_t nod1 = edg[0], nod2 = edg[1];
      if (findParent(nod1) == findParent(nod2)) {
        return edg;
      }
      unionNode(nod1, nod2);
    }
    return vector<int>();
  }
};
int main() {
  Solution sol;
  auto vtOut =
      sol.findRedundantConnection({{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}});
  for (auto n : vtOut) PF("%d,", n);
  PF("\n");
  return 0;
}